public class Part1 {
	
	
	
	
	
	/* ********************************** *
	 * *  Part 1                        * *
	 * ********************************** */
	
	
	
		
	// Task 1.1
	// MSB first
	
	public static boolean increment(int[] vec) {				//Increases the value of a binary vector by 1.
		boolean succ=false;					
		
		for (int i = vec.length - 1 ; i > -1 && !succ ; i--){ 	//We try add 1 to the LSB and use the boolean 'succ' as carry
																
			if (vec[i] < 1){									//if we can add 1 , we do it and the carry is zero. (succ = true)
				vec[i] = vec[i] + 1;
				succ = true;
			
			}else{											   // if we can't add we write in zero and leave the carry as it is.
				vec[i] = 0;
			}
		}
		return succ;
	}		
	
	// Task 1.2
	public static boolean increment(int[][] matrix) {	
		boolean succ=false;
		
		for (int i = matrix.length - 1 ; i > -1 && !succ ; i--){		//we try adding one to each row , if we succeed we return 'true' else we return false; 
			if (increment(matrix[i])){
				succ = true;
			}
		}
		
		return succ;
	}
	
	// calculates the number of '1' in a given matrix starting from a given coordinate and ending in the bottom left corner.
	public static int numberOfOnes (int row ,int column , int[][] matrix){
		int ans = 0;
		int j;
		for (int i = row ; i < matrix.length ; i++){
			if (i == row){								//we want the column index start from the given coordinate only in the first row
				j = column;
			}else{
				j = 0;
			}
			for ( ;j <matrix.length ; j++){				//counting the number of '1'
				if (matrix [i][j] == 1){
					ans = ans + 1;
				}
			}
		}
		return ans;
	}
	
	
	
		
	// Task 1.3	
	// advances the vector to the next binary number with the same amount of '1;
	//returns true if successful.
	
	// **** Aux Functions ****
	
	
		// Aux: Checks if it is possible to move '1' one space left in an array.
			public static boolean canMoveLeft (int [] vec , int index){
				boolean ans = false;
					if (index > 0 && vec[index - 1] == 0){
						ans = true;
					}
				
				return ans;
				
			}
		
		//Aux: Moves '1' one field to the left.
			public static void moveLeft (int [] vec , int index){
				vec[index - 1] = 1;
				vec[index] = 0;
			}
	
	  
			
			
				
	//function that advanced a given binary number to the next number with the same amount of '1'
	public static boolean incrementSameOnes(int[] vec)	{			//wrapper for recursion function incrementSameOnes. 
		boolean succ=false;
		int index = vec.length - 1;
		succ = incrementSameOnes(vec, index);
		return succ;
	}

	//function that advanced a given binary number to the next number with the same amount of '1'
	public static boolean incrementSameOnes(int[] vec , int index){		
		boolean ans = false;
		boolean canMoveLeft = canMoveLeft(vec, index);				
		int numberOfOnes = 0;
		
		if(index == -1){								//we start from the LSB , if we get to the MSB , nothing more can be done.
			ans = false;
		}else{
			if (vec[index] == 1){					 
				if (canMoveLeft){										//if we find '1' that can be moved. we move it and move all the '1' after it to the most left position.
					for (int i = index + 1 ; i < vec.length ;i++){
						if (vec[i] == 1){
							numberOfOnes = numberOfOnes + 1;			// counts the number of '1' to the left of the current index
						}
					}
					moveLeft(vec, index);								// moves the current '1' to the left.
					
					for (int i = vec.length - 1 ; i > index; i--){    // moves the '1' we counted to the most left position.
							if( numberOfOnes != 0 ){
								numberOfOnes = numberOfOnes - 1;
								vec[i] = 1;
							}else{
								vec[i] = 0;
							}
						
					}
					ans = true;
				}else{
					ans = incrementSameOnes(vec, index - 1); 
					}
			}else{
				ans = incrementSameOnes(vec, index - 1);
			}
		}
		return ans;
	}
	
	//Auxiliary converts 2d matrix to a vector
	public static void matrix2Row (int[][] matrix , int[] row){
		int rowIndex = 0;
		for (int i = 0 ; i < matrix.length ; i ++){
			for (int j = 0 ; j < matrix[i].length ; j++){
				row[rowIndex] = matrix[i][j];
				rowIndex = rowIndex + 1;
			}
		}
	}
	// Auxiliary converts a vector to 2d matrix
	public static void row2Matrix (int[][] matrix , int[] row){
		zero2dMatrix(matrix);
		int rowIndex = 0;
		for (int i = 0 ; i < matrix.length ; i ++){
			for (int j = 0 ; j < matrix[i].length ; j++){
				matrix[i][j] = row[rowIndex];
				rowIndex = rowIndex + 1;
			}
		}
	}
	

	
	// Task 1.4
	
	// Aux functions
	// Aux fills a matrix with a given number of '1' starting from the bottom right.
	public static void fillOnes (int row ,int column, int nubmerOfOnes ,int[][] matrix){
		boolean reachRow = false;
		boolean reachColumn = false;
		
		for(int i = matrix.length - 1 ; i > -1 && (!reachRow || !reachColumn)  ; i--){
			if (i == row){
				reachRow = true;
			}
			for (int j = matrix[i].length - 1 ; j > -1 && (!reachRow || !reachColumn) ; j--){
				if (reachRow && j == column){
					reachColumn = true;															//we check if we reached the given coordinate , using reachColumn & reachRow
				}
				if(nubmerOfOnes != 0){
					matrix[i][j] = 1;
					nubmerOfOnes = nubmerOfOnes - 1;
				}else{
					matrix[i][j] = 0;
				}
				
				
			}
		}
	}
	
	//increases the binary number in a 2d matrix to the next number with the same number of '1'
	public static boolean incrementSameOnes(int[][] matrix) {
		boolean succ=false;
		int numberOfOnes = 0;
		for(int i = matrix.length - 1; i > -1 && !succ; i--){
			for (int j = matrix[i].length -1 ;j > -1 && !succ ; j--){                               //loop starts form the bottom right corner of the matrix, and searches for the numbers in a position '01'.
																									//if it is found, we replace the numbers to '10' then we move all the remaining '1' to the most right bottom position
				if(j == 0 && i > 0){																	//If we are positioned in the first column , we can only advance by moving the '1' to the row above us.
					if (matrix[i][j] == 1 && matrix[i -1][matrix[i -1].length - 1] == 0){
						matrix[i - 1][matrix[i -1].length - 1] = 1;
						matrix [i][j] = 0;
						numberOfOnes =numberOfOnes(i, j, matrix);
						fillOnes(i, j, numberOfOnes, matrix);
						succ = true;
					}
				}else{
					if (j !=0 && matrix[i][j] == 1 && matrix[i][j - 1] == 0){							//If we have an empty space to the left of us , we can move the '1' there.
						matrix[i][j - 1] = 1;
						matrix[i][j] = 0;
						numberOfOnes =numberOfOnes(i, j, matrix);
						fillOnes(i, j, numberOfOnes, matrix);
						succ = true;
					}
				}
			}
		}
		return succ;
		}
		
		//		for (int i = matrix.length -1 ; i > -1 && !succ ; i--){
//			if (incrementSameOnes(matrix[i])){
//				succ = true;
//			}else{
//				if (i > 0){
//					for (int j = matrix[i].length - 1; j > -1 ; j-- ){
//						if (canMoveLeft(matrix[i - 1], j)){
//							matrix[i - 1][j] = 1;
//							matrix[i][0] = 0;
//						}
//					}
//				}
//			}
//		}
		
		

//			int[] temp = new int[(matrix.length) * (matrix.length)];
//			matrix2Row(matrix, temp);
//			if (incrementSameOnes(temp)){
//				succ = true;
//			}
//			row2Matrix(matrix, temp);
//		
		
		//			for (int i = matrix.length - 1 ; i > -1 && !succ ; i--){			//We do the increment operation on each line separately. If we are successful, we return 'true' 
//				if (incrementSameOnes(matrix[i])){							//Else we return false.
//					succ = true;
//				}
//			}
		
	
	
	// Auxiliary function that returns an array with the Symmetric coordinates of the input coordinate.
	public static void symetricCoordinate(int[][] matrix , int[] startCoordinate ,int[][] symetricCoordinates){
		int distanceLeftWall = startCoordinate[0];
		int distanceBottomWall = startCoordinate[1];
				
		symetricCoordinates[0] = startCoordinate;
		symetricCoordinates[1][0] = (matrix.length - 1) - distanceBottomWall; 
		symetricCoordinates[1][1] = distanceLeftWall;
		symetricCoordinates[2][0] = (matrix.length - 1) - distanceLeftWall;
		symetricCoordinates[2][1] = (matrix[0].length - 1) - distanceBottomWall;
		symetricCoordinates[3][0] = distanceBottomWall;
		symetricCoordinates[3][1] = (matrix[0].length - 1) - distanceLeftWall;
		
		
		
	}
	
	// Auxiliary: Sums the values of a given coordinates in a given matrix
	public static int sumCoordinates (int[][] symetricCoordinates , int [][] matrix){
		int ans = 0;
		for (int i = 0 ; i < symetricCoordinates.length && ans < 2 ; i++){
			ans = ans+ matrix[symetricCoordinates[i][0]][symetricCoordinates[i][1]];
		}
		return ans;
	}
	
	// Task 1.5
	
	//detects '1' in a given matrix and checks for each '1' if the sum of its symmetric coordinates equals to 1
	public static boolean turnable(int[][] matrix) {
		
		boolean res = true;
		int[][] symetricCoordinates = new int[4][2];  						//array of potential symmetric coordinates
		int[] startCoordinate = {0,0}; 										
		int sum = 0;
		for (int i = 0 ; i < matrix.length && res ; i ++){					//going through the matrix till we find '1'. 
			for (int j = 0 ; j < matrix[i].length && res ; j++){
				if (matrix[i][j] == 1){										//if we find '1' we check its symmetric coordinates and see 
					startCoordinate[0] = i;									//if the sum of the values in those coordinates equals to 1.
					startCoordinate[1] = j;
					symetricCoordinate(matrix, startCoordinate, symetricCoordinates);
					sum = sumCoordinates(symetricCoordinates, matrix);
					if (sum != 1){
						res = false;
					}
					
				}
			}
		}
		
		return res;
	}
	
	/* ********************************** *
	 * *  Part 2                        * *
	 * ********************************** */
	// Task 2.1
	//Goes over the board and checks if there are rectangles with '1' in all of it's conners.
	public static boolean hasSameColorRect(int[][] board) {
		boolean res=false;
		for (int i = 0 ; i < board.length && !res ; i++){				//
			for (int j = 0 ; j < board[0].length && !res; j++){
				if (hasSameColorRect(board, i, j)){
					res = true;
				}
			}
		}
		
		return res;
	}

	// Task 2.2
	//Checks if the board contains a rectangle filled with '1', when the top left coordinate of the rectangle is given. 
	public static boolean hasSameColorRect(int[][] board, int topRow, int leftColumn) {				
		boolean res=false;
			if (board[topRow][leftColumn] == 1){									//if the top left coordinate is not '1' then we are done.
				
				for (int i = topRow + 1 ; i < board.length && !res ; i++){										//a loop that checks all the possible rectangles
					for (int j = leftColumn + 1 ; j < board[0].length && !res ;j++){							//and if the value in all their fields are '1'
						if ((board[topRow][j] == 1) && (board[i][leftColumn] == 1) && (board[i][j] == 1)){		
							res = true;
						}
					}
				}
			}
			
		return res;
	}
	
	/*
	(a) exactly 1/4 the cells are painted with one color
	(b) with 1 color (all cells are painted or not painted): check that no
	rectangle has all corner painted 1
	(c) with one color: check for each cell: if it is painted then its
	rotation by 90,180,270 degree are not painted
			 */
	// Task 2.3
	
	//Checks if board is legally colored with one color
	public static boolean isOneColoring(int[][] board) {
		boolean res=false;
		boolean turnable =  turnable(board);
		boolean hasSameColorRect = hasSameColorRect(board);
			if (turnable && !hasSameColorRect){				
				res = true;
			}
//			if(hasSameColorRect){
//				res = false;
//			}
		return res;
	}
		
	// Task 2.4
	
	//Finds a legally colored board (if possible) with 1 color and (nXn) board when n is even.
	public static int[][] findOneColoring(int n) {
		int[][] matrix=null;
		matrix = new int[n][n];
		zero2dMatrix(matrix);
		boolean solutionFound = false;
		
		int k = (n*n)/4;
		
		for (int i = matrix.length - 1 ; i > -1 && k != 0 ; i --){				//fills the board with 'k' ones.
			for (int j = matrix.length - 1 ; j > -1 && k != 0 ; j--){
				matrix[i][j] = 1;
				k = k - 1;
			}
		}
	if (isOneColoring(matrix)){											//incrementSameOnes changes the matrix , we need to check if the first position fits the solution.
		solutionFound = true;
	}
	
	while (!solutionFound && incrementSameOnes(matrix)){				//while we can advance to a bigger binary number with the same ones we will check if the board is validly colored.
		if (isOneColoring(matrix)){
			solutionFound = true;
		}
	}
		return matrix;
	}
	
	
	/* ********************************** *
	 * *  Part 3                        * *
	 * ********************************** */
	// task 3.1
	// builds 4 colored board from a board which is legally colored with one color.
	public static void buildFourColoring(int[][] matrix) {
		int[][] symetricCoordinates = new int[4][2];
		zero2dMatrix(symetricCoordinates);
		int[] startCoordinates = new int[2];
		
		for (int i = 0 ; i < matrix.length ; i++){						//Basically turns the board and changes the color of the '1' each time it turns
			for (int j = 0 ; j < matrix[i].length ; j++){
				if (matrix[i][j] == 1){
					startCoordinates[0] = i;
					startCoordinates[1] = j;
					symetricCoordinate(matrix, startCoordinates, symetricCoordinates);
						for (int k = 1 ; k < symetricCoordinates.length ; k ++){
							matrix[symetricCoordinates[k][0]][symetricCoordinates[k][1]] = k + 1;
						}
				}
			}
		}
	}

	// task 3.2
	//Finds a legally colored board (if possible) with 4 colors and (nXn) board when n is even.
	public static int[][] findFourColoring(int n) {
		int[][] board=null;
		board = findOneColoring(n);
		buildFourColoring(board);
		return board;
	}


	//Misc Aux functions
	
	// Auxiliary function that puts zeros in all fields of a 2d array.
		public static void zero2dMatrix(int[][] matrix){
			for(int i = 0 ; i < matrix.length ; i++){
				for (int j = 0 ; j < matrix[i].length ; j++){
					matrix[i][j] = 0;
				}
			}
		}
	
	
	/* ********************************** *
	 * *  Main you may want to use      * *
	 * ********************************** */

		public static void main(String[] args) {
		int n=4;
		long startTime=System.currentTimeMillis();
		int[][] sol=findOneColoring(n);
		printMatrix(sol);
		long endTime=System.currentTimeMillis();
		System.out.println("Solution time : "+(endTime-startTime)+" ms");
		System.out.println("Solution found: "+(sol!=null));
		if(sol!=null) {
			System.out.println("Valid solution: "+isOneColoring(sol));
		}
		buildFourColoring(sol);
		printMatrix(sol);
		
		/*internal 
		int[] test0 = { 1, 1, 0, 0 };
		int[] test1 = { 1, 1, 1, 0 };
		int[] test3 = { 0, 0, 0, 0 };
		int[] test4 = { 1, 1, 1, 1 };
		
		System.out.println(increment(test0));
		System.out.println(increment(test1));
		
//		while (increment(test3)){
//			printVector(test3);
//		}
		increment(test4);
		printVector(test4);
		
		// End test of increment
		System.out.println();
		System.out.println();
		int[][] testIncremet2d = {{0,0,0},{0,0,0},{0,0,0}};

//		while (increment(testIncremet2d)){
//			printMatrix(testIncremet2d);
//			System.out.println();
//		}
		
		int[] symTestCordinate = {1,2};
		int[][] symTestMatrix = new int[8][8];
		zero2dMatrix(symTestMatrix);
		System.out.println();
		printMatrix(symTestMatrix);
		System.out.println();
		symTestMatrix[symTestCordinate[0]][symTestCordinate[1]] = 1;
		printMatrix(symTestMatrix);
		System.out.println();
		int[][] ans = new int[4][2];
		zero2dMatrix(ans);
		symetricCoordinate(symTestMatrix, symTestCordinate, ans);
		for (int i = 0 ; i < ans.length ; i++){
			symTestMatrix[ans[i][0]][ans[i][1]] = 1;
		}
		printMatrix(symTestMatrix);
		System.out.println();
		printMatrix(ans);
		
		
		*/
		
		testIncrement1d();
		testIncrement2d();
		testIncrementSameOnes1d();
		testIncrementSameOnes2d();
		testTurnable();
		
		
		//hasSameColorRect test 
		/*
		int[][] testMatrix = new int[4][4];
		zero2dMatrix(testMatrix);
		testMatrix[0][1] = 1;
		testMatrix[0][3] = 1;
		testMatrix[2][1] = 1;
		testMatrix[2][3] = 1;
		System.out.println();
		printMatrix(testMatrix);
		System.out.println(hasSameColorRect(testMatrix, 0, 0) +" <== This should be 'false'");
		System.out.println(hasSameColorRect(testMatrix, 0, 1) +" <== This should be 'true'");
		testMatrix[0][0] = 1;
		System.out.println(hasSameColorRect(testMatrix, 0, 0) + " <== This should be false");
		
		System.out.println(hasSameColorRect(testMatrix) +" <== This should be 'true'");
		zero2dMatrix(testMatrix);
		printMatrix(testMatrix);
		testMatrix[0][1] = 1;
		testMatrix[0][3] = 1;
		printMatrix(testMatrix);
		System.out.println(hasSameColorRect(testMatrix) +" <== This should be 'false'");
		testMatrix[2][1] = 1;
		testMatrix[2][3] = 1;
		printMatrix(testMatrix);
		System.out.println(hasSameColorRect(testMatrix) +" <== This should be 'true'");
		zero2dMatrix(testMatrix);
		printMatrix(testMatrix);
		testMatrix[2][2] = 1;
		testMatrix[3][2] = 1;
		testMatrix[2][3] = 1;
		testMatrix[3][3] = 1;
		printMatrix(testMatrix);
		System.out.println(hasSameColorRect(testMatrix) +" <== This should be 'true'");
		*/
		testHasSameColorRect();
		testHasSameColorRectLeftCorner();
		testIsOneColoring(); 
		
		//Test Find One Coloring
		printMatrix(findOneColoring(8));
		//End Test
		
		
//		int[] vec = new int[8];
//		vec[7] = 1;
//		vec[6] = 1;
//		vec[3] = 1;
//		printVector(vec);
//		while (incrementSameOnes(vec)){
//			printVector(vec);
//		}
		
		
//		zero2dMatrix(testMatrix);
//		testMatrix[3][3] = 1;
//		testMatrix[3][2] = 1;
//		testMatrix[3][1] = 1;
//		while (incrementSameOnes(testMatrix)){
//			printMatrix(testMatrix);
//		}
		
		//Test Find One Coloring
//				printMatrix(findOneColoring(4));
//				printMatrix(findOneColoring(6));
//				printMatrix(findOneColoring(12));
		//End Test
		
		
		testBuildFourColoring();
	}

	
	public static boolean eqVec1d(int[] exp,int[] res) {
		for (int i=0;i<res.length;i++)  
				if (res[i]!=exp[i]) return false;
		return true;
	}
	
	public static boolean eqVec2d(int[][] exp,int[][] res) {
		for (int i=0;i<res.length;i++)  
			if (!eqVec1d(res[i],exp[i])) return false;
		return true;
	}
	
	public static void testIncrement1d() {
		int[][] vec =new int[][] {{ 0, 1, 1, 1, 1 },{1, 0, 1, 1, 0},{1, 1, 1, 1, 1}};
		int[][] res= new int[][] {{1, 0, 0, 0, 0 },{1, 0, 1, 1, 1},{0, 0, 0, 0, 0}};
		boolean[] resB= new boolean[] {true,true,false};
		for(int i =0;i<3;i++) 
			if ( increment(vec[i])!=resB[i] || !eqVec1d(vec[i],res[i])) { 
				System.out.println("test_increment_1d_"+i+" faild");
				return;
			}
		System.out.println("test_increment_1d succeeded");
	}

	public static void testIncrement2d() {
		int [][][] matrix={{{0,1,0},{1,1,0},{0,1,1}},{{0,0,1},{0,0,1},{1,1,1}},{{1,1,1},{1,1,1},{1,1,1}}}; 	
		int [][][] res   ={{{0,1,0},{1,1,0},{1,0,0}},{{0,0,1},{0,1,0},{0,0,0}},{{0,0,0},{0,0,0},{0,0,0}}};
		boolean[] resB= new boolean[] {true,true,false};
		for(int i =0;i<3;i++) 
			if (increment(matrix[i])!=resB[i] || !eqVec2d(matrix[i],res[i])) { 
				System.out.println("test_increment_2d_"+i+" faild");
				return;
			}
		System.out.println("test_increment_2d succeeded");
	}
	
	public static void testIncrementSameOnes1d() {
		int[][] vec =new int[][] {{0,0,0,1,1,0,0,1,1},{1,0,1,0,0,1,1,1,1}, {1,1,1,1,1,0,0,0,0}};
		int[][] res= new int[][] {{0,0,0,1,1,0,1,0,1},{1,0,1,0,1,0,1,1,1},null};
		boolean[] resB= new boolean[] {true,true,false};
		for(int i =0;i<3;i++) 
			if (incrementSameOnes(vec[i])!=resB[i] || (res[i]!=null && !eqVec1d(vec[i],res[i]))){
				System.out.println("test_incrementSameOnes_1d_"+i+" faild");
				return;
			}
		System.out.println("test_incrementSameOnes_1d succeeded");
	}
	
	public static void testIncrementSameOnes2d() {
		int [][][] matrix={{{0,0,0},{1,1,0},{0,1,1}},{{1,0,1},{0,0,1},{1,1,1}},{{1,1,1},{1,1,0},{0,0,0}}}; 	
		int [][][] res   ={{{0,0,0},{1,1,0},{1,0,1}},{{1,0,1},{0,1,0},{1,1,1}},null};
		boolean[] resB= new boolean[] {true,true,false};
		for(int i =0;i<3;i++) 
			if (incrementSameOnes(matrix[i])!=resB[i] || (res[i]!=null && !eqVec2d(matrix[i],res[i]))) { 
				System.out.println("test_incrementSameOnes_2d_"+i+" faild");
				return;
			}
		System.out.println("test_incrementSameOnes_2d succeeded");
	}

	public static void testTurnable() {
		int[][][] matrix = {{{ 0, 0 ,0, 0 },{ 1, 1 ,1 ,0 },{ 1, 0, 0 ,0 },{ 0, 0 ,0 ,0 }},
				 			{{ 0, 0, 0, 0 },{ 1, 1, 0, 0 },{ 1, 1, 0, 0 },{ 0, 0, 0, 0 }},
				 			{{ 1, 1, 0, 0 },{ 1, 1, 0, 0 },{ 0, 0, 0, 0 },{ 0, 0 ,0 ,0 }},
				 			{{ 0, 0, 0, 0 },{ 1, 0, 0, 0 },{ 1, 1, 0, 0 },{ 1, 0, 0, 0 }}};
		boolean[] resB= new boolean[] {false,false,true,true};
		for (int  i=0;i<matrix.length;i++) {
			if (turnable(matrix[i])!=resB[i]) { 
				System.out.println("test_turnable_"+i+" faild");
				return;
			}
		}
		System.out.println("test_turnable succeeded");

	}
	
	public static void testHasSameColorRect(){
		int[][][] matrix = {{{ 0, 1, 0, 1 },{ 0, 0, 0, 0 },{ 0, 1, 0, 1 },{ 0, 0, 0, 0 }},
							{{ 0, 1, 0, 0 },{ 1, 0, 0, 1 },{ 0, 1, 0, 1 },{ 0, 1, 0, 0 }}};
		boolean[] resB= new boolean[] {true,false};
		for (int  i=0;i<matrix.length;i++) {
			if (hasSameColorRect(matrix[i])!=resB[i]) {
				System.out.println("test_hasSameColorRect_"+i+" faild");
				return;
			}
		}	
		System.out.println("test_hasSameColorRect succeeded");
	}
	
	public static void testHasSameColorRectLeftCorner(){
		int[][] matrix = {{ 0, 1, 0, 1 },{ 0, 0 ,0 ,0 },{ 0, 1, 0, 1 },{ 0 ,0 ,0 ,0 }};
		int[][] leftCorner ={{0,0},{0,1}};
		boolean[] resB= new boolean[] {false,true};
		for (int  i=0;i<leftCorner.length;i++) {
			if (hasSameColorRect(matrix,leftCorner[i][0],leftCorner[i][1])!=resB[i]) { 
				System.out.println("test_hasSameColorRect_LeftCorner_"+i+" faild");
				return;
			}
		}	
		System.out.println("test_hasSameColorRect_LeftCorner succeeded");
	}

	public static void testIsOneColoring(){
		int[][][] matrix = {{{ 1, 1, 0, 0 },{ 0, 1, 1, 0 },{ 0, 0, 0, 0 },{ 0, 0, 0, 0 }},
							{{ 0, 1, 0, 1 },{ 0, 0, 0, 0 },{ 0, 1, 0, 1 },{ 0, 0, 0, 0 }},
							{{ 0, 0, 0, 1 },{ 0, 0, 1, 1 },{ 0, 0, 0, 1 },{ 0, 0, 0, 0 }},
							{{ 1, 1, 1, 0 },{ 0, 1, 0, 0 },{ 0, 0, 0, 0 },{ 0, 0, 0, 0 }}};
		boolean[] resB= new boolean[] {false,false,true,true};
		for (int  i=0;i<matrix.length;i++) {
			if (isOneColoring(matrix[i])!=resB[i]) {
				System.out.println("test_isOneColoring_"+i+" faild");
				return;
			}
		}	
		System.out.println("test_isOneColoring succeeded");
	}
	
	public static void testBuildFourColoring(){
		int[][] matrix = {{ 1, 1, 1, 0 },{ 0, 1, 0, 0 },{ 0, 0, 0, 0 },{ 0, 0, 0, 0 }};
		int[][][] res = {{{ 1, 1, 1, 2 },{ 3, 1, 2, 2 },{ 3, 3, 4, 2 },{ 3, 4, 4, 4 }},
						 {{ 1, 1, 1, 2 },{ 4, 1, 2, 2 },{ 4, 4, 3, 2 },{ 4, 3, 3, 3 }},
						 {{ 1, 1, 1, 3 },{ 2, 1, 3, 3 },{ 2, 2, 4, 3 },{ 2, 4, 4, 4 }},
						 {{ 1, 1, 1, 3 },{ 4, 1, 3, 3 },{ 4, 4, 2, 3 },{ 4, 2, 2, 2 }},
						 {{ 1, 1, 1, 4 },{ 2, 1, 4, 4 },{ 2, 2, 3, 4 },{ 2, 3, 3, 3 }},
				         {{ 1, 1, 1, 4 },{ 3, 1, 4, 4 },{ 3, 3, 2, 4 },{ 3, 2, 2, 2 }}};
		boolean eq=false;
		for (int i=0; i< res.length;i++ ) {
			buildFourColoring(matrix);
			if (eqVec2d(matrix,res[i])) eq=true;
			matrix = new int[][] {{ 1, 1, 1, 0 },{ 0, 1, 0, 0 },{ 0, 0, 0, 0 },{ 0, 0, 0, 0 }};
		}
		if (!eq) System.out.println("test_buildFourColoring faild");
		else	 System.out.println("test_buildFourColoring succeeded");
	}

	public static void printVector (int[] vector){
		System.out.print('{');
		for (int i = 0 ; i < vector.length ; i++){
			System.out.print(vector[i]);
		}
		System.out.print('}');
	}
	
	public static void printMatrix (int[][] matrix){
		System.out.println();
		for (int i = 0 ; i < matrix.length ; i++){
			printVector(matrix[i]);
			System.out.println();
		}
	}
	
	
//	public static void main (String[] args){
	
	// Start of test for increment	
	
//}
	
}
